#-*-coding:UTF-8-*-

import types


def print_quick_sort(data, b, i, j, width=3, debug=False):
    if not debug:
        return
    strs = []
    tags = []
    for index, a in enumerate(data):
        s = str(a)
        if len(s) < width:
            s = ' ' * (width-len(s)) + s
        strs.append(s)
        if index == b:
            tags.append(' '*(width-1)+'^')
        elif index == i:
            tags.append(' '*(width-1)+'i')
        elif index == j:
            tags.append(' '*(width-1)+'j')
        else:
            tags.append(' '*width)
    if i == j:
        msg = 'i == j = %s'%i
    elif b == i:
        msg = 'b == i = %s'%b
    elif b == j:
        msg = 'b == j = %s'%b
    else:
        msg = ''
    print('[ %s ]\n  %s  %s'%(','.join(strs), ' '.join(tags), msg))


def _quick_sort_action(data, start, end, debug=False):
    if debug:
        print('[ start=%s  end=%s ]'%(start, end))
    i, j = start+1 ,end
    if i == j:
        if data[start] > data[i]:
            #switch
            print_quick_sort(data, start, i, j, debug=debug)
            data[start], data[i] = data[i], data[start]
            print_quick_sort(data, start, i, j, debug=debug)
        return
    elif i > j:
        return
    while i < j:
        while j >= i and data[start] <= data[j]:
            j -= 1
        while j >= i and data[start] >= data[i]:
            i += 1
        if i < j:
            print_quick_sort(data, start, i, j, debug=debug)
            data[i], data[j] = data[j], data[i]
            print_quick_sort(data, start, i, j, debug=debug)
        elif i == j:
            if data[start] <= data[i]:
                i -= 1
            print_quick_sort(data, start, i, j, debug=debug)
            data[start], data[i] = data[i], data[start] # data exchange
            print_quick_sort(data, start, i, j, debug=debug)
        else:
            print_quick_sort(data, start, i, j, debug=debug)
            data[start], data[j] = data[j], data[start]
            i = j
            print_quick_sort(data, start, i, j, debug=debug)
    _quick_sort_action(data, start, i-1, debug=debug)
    _quick_sort_action(data, i+1, end, debug=debug)


def quick_sort(data, debug=False):
    '''quick sort algorithm.  author: zhaoxp
    '''
    assert hasattr(data, '__setitem__')
    _quick_sort_action(data, 0, len(data)-1, debug=debug)
